package link;

import java.util.HashMap;
import java.util.Map;

public class CopyListWithRandomPointer138 {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        Node index = head;
        Node newHead = new Node(head.val);
        Node nHead = newHead;
        Map<Node,Node> map = new HashMap<>();
        map.put(head,newHead);
        while (index.next!=null){
            nHead.next = new Node(index.next.val);
            map.put(index.next,nHead.next);
            nHead = nHead.next;
            index = index.next;
        }
        index = head;
        nHead = newHead;

        while (index!=null){

            nHead.random = map.get(index.random);

            index = index.next;
            nHead = nHead.next;
        }
        return newHead;
    }
}
